package LeetCode._01算法入门.day09广度深度优先搜索;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 挚爱之夕
 * @date 2022-02-28 - 02 - 28 - 17:08
 * @Description 在给定的m x n网格grid中，每个单元格可以有以下三个值之一：
 * 值0 代表空单元格；
 * 值1 代表新鲜橘子；
 * 值2 代表腐烂的橘子。
 * 每分钟，腐烂的橘子周围4个方向上相邻的新鲜橘子都会腐烂。
 * 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回-1。
 * @Version 中等
 */
public class _944腐烂的橘子 {
    static int[][] grid = {
            {2, 1, 1},
            {1, 1, 0},
            {0, 1, 1}
    };
    @Test
    public void solve(){
        int res = orangesRotting(grid);
        System.out.println(res);
    }
    static int[][] dir = new int[][]{
            {0, -1},
            {0, 1},
            {-1, 0},
            {1, 0}
    };
    public int orangesRotting(int[][] grid) {
        //没有新鲜的橘子
        if(noFreshOrange(grid)){
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;
        int minute = 0;
        Queue<int[]> badOranges = new LinkedList<>();
        //记录所有坏橘子
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j] == 2){
                    badOranges.offer(new int[]{i, j});
                }
            }
        }
        //橘子的坐标
        int x1, y1;
        //每次有可能感染新鲜橘子的坏橘子个数
        int size;
        //一维数组存储了橘子的坐标
        int[] orange;
        while(!badOranges.isEmpty()){
            size = badOranges.size();

            //已经存下的坏橘子都要感染其他
            while(size != 0){
                //出队
                orange = badOranges.poll();
                int x = orange[0];
                int y = orange[1];
                //四个方向
                for (int[] d:dir
                ) {
                    x1 = x + d[0];
                    y1 = y + d[1];
                    if(x1 >= 0 && x1 < m && y1 >= 0 && y1 < n && grid[x1][y1] == 1){//新鲜橘子
                        grid[x1][y1] = 2;//感染
                        badOranges.offer(new int[]{x1, y1});//这个橘子可能感染其他的
                    }
                }
                size--;
            }
            minute++;
        }
        if(noFreshOrange(grid)){
            //多算的一分钟
            minute--;
            return minute;
        }

        return -1;
    }
    public boolean noFreshOrange(int[][] grid){
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == 1){
                    return false;
                }
            }
        }
        return true;
    }
}
